package mrHunter.lib;

import java.util.Arrays;


public class Graph {
    //邻接矩阵存储
    private int v;
    private int[][]edges;

    public boolean isConnected(){
        boolean[] visited=new boolean[v];
        for(int i=0;i<v;i++)
            visited[i]=false;
        int count=0;
        for (int i=0;i<v;i++){
            if(!visited[i]){
                DFS(i,visited,edges);
                count++;
            }
        }
        if(1==count)
            return true;
        else
            return false;
    }

    private void DFS(int i, boolean[] visited, int[][]G){
        for(int j=0;j<visited.length;j++){
            if(1==G[i][j]&&!visited[j]){
                visited[j]=true;
                DFS(j,visited,G);
            }
        }
    }

    public Graph() {}

    public Graph(Graph G){
        this.v=G.v;
        this.edges=new int[v][v];
        //this.edges=G.edges.clone();

        for(int i=0;i<v;i++){
            //for(int j=0;j<v;j++){
            this.edges[i]=G.edges[i].clone();
            //}
        }
    }

    public Graph(int[][] edges){
        if(edges!=null){
            this.v=edges[0].length;
            this.edges=edges;
        }
    }

    /*public void printGraph(){
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                System.out.print(edges[i][j]+" ");
            }
            System.out.println("\n");
        }
    }*/

    //get the number of vertex
    public int getVertexNum() { return v; }

    //whether there is edge between v1 and v2
    public boolean hasEdge(int v1, int v2){
        if(v1>=v||v2>=v||v1<0||v2<0)
            return false;
        else
            return (edges[v1][v2]!=0);
    }

    //add edge between v1 and v2
    public Graph addEdge(int v1, int v2){
        Graph res=new Graph(this);
        if(v1>=v||v2>=v||v1<0||v2<0)
            return res;
        else{
            res.edges[v1][v2]=1;
            res.edges[v2][v1]=1;
        }
        return res;
    }

    //delete edge between v1 and v2
    public Graph deleteEdge(int v1, int v2){
        Graph res=new Graph(this);
        if(v1>=v||v2>=v||v1<0||v2<0)
            return res;
        else{
            res.edges[v1][v2]=0;
            res.edges[v2][v1]=0;
        }
        return res;
    }

    //add vertex
    public Graph addVertex(int num, int type){
        //type: 1 random, 2 empty, 3 all
        int[][] temp=new int[v+num][v+num];
        for(int i=0;i<v;i++){
            temp[i]= Arrays.copyOf(temp[i],v);
        }
        for(int i=v;i<v+num;i++){
            for (int j=0;j<i;j++){
                temp[i][j]=0;
                temp[j][i]=temp[i][j];
            }
        }
        return new Graph(temp);
    }

    //delete vertex
    //TODO:delete specific vertex
    public Graph deleteVertex(int num){
        int[][] temp;
        if(num<v){
            temp=new int[v-num][v-num];
            for(int i=0;i<v-num;i++){
                //for (int j=0;j<v-num;j++)
                temp[i]=Arrays.copyOf(edges[i],v-num);
            }
            return new Graph(temp);
        }
        else {
            return new Graph(new int[1][1]);
        }
    }

    //complement of graph
    public Graph complement(){
        Graph res=new Graph(this);
        for(int i=0;i<v;i++){
            for(int j=0;j<i;j++){
                if(0==edges[i][j])
                    res.edges[j][i]=res.edges[i][j]=1;
                else
                    res.edges[j][i]=res.edges[i][j]=0;
            }
        }
        return res;
    }

    public int[][] getEdges() { return edges; }
    /*
    public void setVertexNum(int v) { this.v = v; }



    public void setEdges(int[][] edges) { this.edges = edges; }

    public  Graph addEdge(){ return addEdge(1); }

    public Graph addEdge(int num){
        Graph res=new Graph(this);
        int temp=0;
        for(int i=0;i<res.v;i++){
            for(int j=i+1;j<res.v;j++){
                if(res.edges[i][j]==0){
                    res.edges[i][j]=1;
                    res.edges[j][i]=1;
                    temp++;
                    if(temp==num) return res;
                }
            }
        }
        return res;
    }

    public Graph deleteEdge(){return deleteEdge(1);}

    public Graph deleteEdge(int num){
        Graph res=new Graph(this);
        int temp=0;
        for(int i=0;i<res.v;i++){
            for(int j=i+1;j<res.v;j++){
                if(res.edges[i][j]==1){
                    res.edges[i][j]=0;
                    res.edges[j][i]=0;
                    temp++;
                    if(temp==num) return res;
                }
            }
        }
        return res;
    }

    public Graph addVertex(){return addVertex(1,1); }

    public Graph addVertex(int num){return addVertex(num,1);}

    public Graph deleteVertex(){return deleteVertex(1);}



    public Graph complement(){
        Graph res=new Graph(this);
        for(int i=0;i<v;i++){
            for(int j=0;j<i;j++){
                if(0==edges[i][j])
                    res.edges[j][i]=res.edges[i][j]=1;
                else
                    res.edges[j][i]=res.edges[i][j]=0;
            }
        }
        return res;
    }*/
}